package data_structure;

public class leetcode_0021 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p=list1;ListNode q=list2;
        if(list1==null) {
            return q;

        }
        if(list2==null) return p;
        ListNode head=new ListNode();
        if(p.val>q.val) {head=q;q=q.next;}
        else{
            head=p;p=p.next;
        }
        ListNode r=head;
        while(p!=null&&q!=null){
            if(p.val<q.val){
                r.next=p;
                p=p.next;
                r=r.next;
            }
            else{
                r.next=q;
                q=q.next;
                r=r.next;
            }
        }
        while(p!=null){
            r.next=p;
            p=p.next;
            r=r.next;
        }
        while(q!=null){
            r.next=q;
            q=q.next;
            r=r.next;
        }
        return head;
    }
}
//class ListNode {
//    int val;
//    ListNode next;
//    ListNode() {}
//    ListNode(int val) { this.val = val; }
//    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//}